home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / poly3d-r / scandata.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  16.5 KB  |  533 lines
  1. /*****************************************************************************
  2. *   Routines to    scan convert the input (polygons), which is sorted into         *
  3. * global hash table PolyHashTable according to polygons Ymin.             *
  4. *                                         *
  5. * Written by:  Gershon Elber                Ver 2.0, Mar. 1990   *
  6. *****************************************************************************/
  7.  
  8. #ifdef __MSDOS__
  9. #include <stdlib.h>
  10. #endif /* __MSDOS__ */
  11.  
  12. #include <math.h>
  13. #include <time.h>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include "program.h"
  17. #include "iritprsr.h"
  18.  
  19. /* #define DEBUG1               Add some printing to stderr routines. */
  20.  
  21. #define Z_BUFFER_MIN_Z    -32767
  22.  
  23. static GifPixelType *MaskSubScanLine = NULL;
  24. static GifPixelType *ImageScanLine = NULL;
  25. static GifPixelType *MaskScanLine = NULL;
  26. static int *ZBuffer;
  27.  
  28. static void InitScanLine(void);
  29. static void ScanOnePolygon(IPPolygonStruct *PPolygon, int Level);
  30. static IPVertexStruct *GetNeighborVrtx(IPPolygonStruct *PPolygon,
  31.                        IPVertexStruct *V, IPVertexStruct *NotV);
  32. static void UpdateScanLine(int x1, int z1, int x2, int z2,
  33.                         int Color1, int Color2);
  34.  
  35. #ifdef DEBUG1
  36. void PrintHashTable(void);
  37. void PrintPolygon(IPPolygonStruct *PPolygon);
  38. void PrintImageScanLine(void);
  39. #endif /* DEBUG1 */
  40.  
  41. /*****************************************************************************
  42. * Routine to scan convert all polygons in PolyHashTable.             *
  43. * The real images goes to GifFile, while GifMask (if not NULL) will have a   *
  44. * booleam mask, where image was created.                     *
  45. *****************************************************************************/
  46. void ScanConvertData(GifFileType *GifFile, GifFileType *GifMask)
  47. {
  48.     char *ImageSubBGScanLine;
  49.     int i, j, k, OrigScrnXSize, OrigScrnYSize, *ImageSubScanLine,
  50.     SubSamplePixelSquare, *MinIntensityIndex, SubSamplePixel,
  51.     MinYScan = 0, SubSampleLine = 0, LineCount = 0;
  52.     long SaveTime = time(NULL);
  53.     IPPolygonStruct *PPolygon, *PPolygonLast;
  54.     GifPixelType *OneSubScanLine;
  55.  
  56.     OrigScrnXSize = GlblShadeInfo.ScrnXSize;
  57.     OrigScrnYSize = GlblShadeInfo.ScrnYSize;
  58.  
  59.     GlblShadeInfo.ScrnXSize *= GlblShadeInfo.SubSamplePixel;
  60.     GlblShadeInfo.ScrnYSize *= GlblShadeInfo.SubSamplePixel;
  61.  
  62.     if (GlblShadeInfo.SubSamplePixel > 1) {
  63.     OneSubScanLine = (GifPixelType *) IritMalloc(sizeof(GifPixelType) *
  64.                              OrigScrnXSize);
  65.     ImageSubScanLine = (int *) IritMalloc(sizeof(int) *
  66.                           OrigScrnXSize);
  67.     ImageSubBGScanLine = (char *) IritMalloc(sizeof(char) *
  68.                          OrigScrnXSize);
  69.     }
  70.     ImageScanLine = (GifPixelType *) IritMalloc(sizeof(GifPixelType) *
  71.                         GlblShadeInfo.ScrnXSize);
  72.     if (GifMask != NULL) {
  73.     if (GlblShadeInfo.SubSamplePixel > 1)
  74.         MaskSubScanLine = (GifPixelType *)
  75.         IritMalloc(sizeof(GifPixelType) * OrigScrnXSize);
  76.     MaskScanLine = (GifPixelType *) IritMalloc(sizeof(GifPixelType) *
  77.                            GlblShadeInfo.ScrnXSize);
  78.     }
  79.     ZBuffer = (int *) IritMalloc(sizeof(int) * GlblShadeInfo.ScrnXSize);
  80.  
  81.     MinIntensityIndex = GlblShadeInfo.MinIntensityIndex;
  82.     SubSamplePixel = GlblShadeInfo.SubSamplePixel;
  83.     SubSamplePixelSquare = SQR(SubSamplePixel);
  84.  
  85.     fprintf(stderr, "\nPass 4, Level [%4d] =      ",
  86.         OrigScrnYSize);
  87.  
  88.     for (i = 0; i < GlblShadeInfo.ScrnYSize; i++) {         /* Scan line i: */
  89.     /* First lets scan and delete all polygons below this scan line: */
  90.     for (j = MinYScan; j <= i; j++) {
  91.         PPolygon = PPolygonLast = PolyHashTable[j];
  92.         while (PPolygon) {
  93.         if (PPolygon -> BBox[1][1] < i) {    /* Delete this polygon. */
  94.             /* If it is first one, update the hash table also. Note  */
  95.             /* we dont free the polygon as, we are not going to      */
  96.             /* allocate anything any more, so why bather.         */
  97.             if (PPolygon == PolyHashTable[j])
  98.             PolyHashTable[j] = PPolygonLast = PPolygon =
  99.                 PPolygon -> Pnext;
  100.             else
  101.             PPolygonLast -> Pnext = PPolygon = PPolygon -> Pnext;
  102.         }
  103.         else {
  104.             PPolygonLast = PPolygon;
  105.             PPolygon = PPolygon -> Pnext;
  106.         }
  107.         }
  108.         /* If this level is empty - advance the minimum level to scan: */
  109.         if (j == MinYScan && PolyHashTable[j] == NULL)
  110.         MinYScan++;
  111.     }
  112.  
  113.     /* New do the scan conversion of the active polygons: */
  114.     InitScanLine();
  115.     for (j = MinYScan; j <= i; j++) {
  116.         PPolygon = PPolygonLast = PolyHashTable[j];
  117.         while (PPolygon) {
  118.         ScanOnePolygon(PPolygon, i);
  119.         PPolygonLast = PPolygon;
  120.         PPolygon = PPolygon -> Pnext;
  121.         }
  122.     }
  123.  
  124.     if (SubSamplePixel > 1) {
  125.         if (SubSampleLine == 0) {      /* Reset the sub sumpling buffers. */
  126.         memset(ImageSubScanLine, 0,
  127.             sizeof(int) * OrigScrnXSize);
  128.         memset(OneSubScanLine, 0,
  129.             sizeof(GifPixelType) * OrigScrnXSize);
  130.         memset(ImageSubBGScanLine, 0,
  131.                    sizeof(char) * OrigScrnXSize);
  132.         if (GifMask)
  133.             memset(MaskSubScanLine, 0,
  134.                sizeof(GifPixelType) * OrigScrnXSize);
  135.         }
  136.         for (j = 0; j < GlblShadeInfo.ScrnXSize; j++)
  137.         if (ImageScanLine[j] == 0)
  138.             ImageSubBGScanLine[j / SubSamplePixel]++;
  139.         else {
  140.             k = j / SubSamplePixel;
  141.             ImageSubScanLine[k] += ImageScanLine[j];
  142.             OneSubScanLine[k] = ImageScanLine[j];
  143.             if (GifMask)
  144.             MaskSubScanLine[k] = MaskScanLine[j] != 0 ||
  145.                                MaskSubScanLine[k];
  146.         }
  147.         SubSampleLine++;
  148.         if (SubSampleLine == SubSamplePixel) {
  149.         for (j = 0; j < OrigScrnXSize; j++) {
  150.             /* Instead of Back Ground - add the lowest intensity of */
  151.             /* This color. Note we still may have problems if two   */
  152.             /* colors are averaged to a color index in between...   */
  153.             if (ImageSubScanLine[j] > 0)
  154.             ImageSubScanLine[j] += ImageSubBGScanLine[j] *
  155.                     MinIntensityIndex[OneSubScanLine[j]];
  156.             OneSubScanLine[j] = ImageSubScanLine[j] /
  157.                             SubSamplePixelSquare;
  158.         }
  159.         fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
  160.  
  161. #            ifndef DEBUG_NO_GIF
  162.             EGifPutLine(GifFile, OneSubScanLine,
  163.                 OrigScrnXSize);
  164.             if (GifMask)
  165.             EGifPutLine(GifMask, MaskSubScanLine,
  166.                     OrigScrnXSize);
  167. #            endif /* DEBUG_NO_GIF */
  168.  
  169.         SubSampleLine = 0;
  170.         }
  171.     }
  172.     else {
  173.         fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
  174.  
  175. #        ifndef DEBUG_NO_GIF
  176.         EGifPutLine(GifFile, ImageScanLine, GlblShadeInfo.ScrnXSize);
  177.         if (GifMask)
  178.             EGifPutLine(GifMask, MaskScanLine,
  179.                 GlblShadeInfo.ScrnXSize);
  180. #        endif /* DEBUG_NO_GIF */
  181.     }
  182.     }
  183.  
  184.     fprintf(stderr, ",  %ld seconds.", time(NULL) - SaveTime);
  185. #ifdef AMIGA
  186.     fflush(stderr);
  187. #endif /* AMIGA */
  188.  
  189.     GlblShadeInfo.ScrnXSize = OrigScrnXSize;
  190.     GlblShadeInfo.ScrnYSize = OrigScrnYSize;
  191. }
  192.  
  193. /*****************************************************************************
  194. * Reset all buffers to clear state:                         *
  195. *****************************************************************************/
  196. static void InitScanLine(void)
  197. {
  198.     memset(ImageScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);
  199.  
  200.     if (MaskScanLine)
  201.         memset(MaskScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);
  202.  
  203.     /* Set all Zbuffer to Z_BUFFER_MIN_Z. Can be done in a regular loop as:  */
  204.     /* for (i = 0; i < ScrnXSize; i++) ZBuffer[i] = Z_BUFFER_MIN_Z;         */
  205.     /* As memset allows setting of only one byte, the minimum we can set     */
  206.     /* here is -32640 which is 0x8080, so we do that instead:             */
  207.     memset(ZBuffer, 0x80, sizeof(int) * GlblShadeInfo.ScrnXSize);
  208. }
  209.  
  210. /*****************************************************************************
  211. * Scan convert one polygon:                             *
  212. * 1. If one of the left/right boundaries is found to be below current level  *
  213. *    that boundary edge is updated.                         *
  214. * 2. Interpolate the Color and Z value of the intersection of scan line with *
  215. *    the boundaries and call UpdateScanLine to update the buffers.         *
  216. *****************************************************************************/
  217. static void ScanOnePolygon(IPPolygonStruct *PPolygon, int Level)
  218. {
  219.     int x1, z1, x2, z2, Color1, Color2;
  220.     RealType t1, t2, *Coord1, *Coord2;
  221.     IPVertexStruct *V;
  222.     PolygonScanConvertStruct
  223.     *PScan = (PolygonScanConvertStruct *) PPolygon -> PAux;
  224.  
  225.     /* Stage 1 - verify that both boundaries are in range: */
  226.     if (PScan -> Bndry1.MaxEdgeY < Level) {
  227.     V = PScan -> Bndry1.VMinY;
  228.     PScan -> Bndry1.VMinY = PScan -> Bndry1.VMaxY;
  229.     PScan -> Bndry1.VMaxY =
  230.         GetNeighborVrtx(PPolygon, PScan -> Bndry1.VMaxY, V);
  231.     PScan -> Bndry1.MaxEdgeY =
  232.         (int) PScan -> Bndry1.VMaxY -> Coord[1];
  233.     }
  234.  
  235.     if (PScan -> Bndry2.MaxEdgeY < Level) {
  236.     V = PScan -> Bndry2.VMinY;
  237.     PScan -> Bndry2.VMinY = PScan -> Bndry2.VMaxY;
  238.     PScan -> Bndry2.VMaxY =
  239.         GetNeighborVrtx(PPolygon, PScan -> Bndry2.VMaxY, V);
  240.     PScan -> Bndry2.MaxEdgeY =
  241.         (int) PScan -> Bndry2.VMaxY -> Coord[1];
  242.     }
  243.  
  244.     /* Stage 2 - evaluate the interpolated X & Z for this line and call      */
  245.     /* UpdateScanLine with them. Note we could do it using some sort of DDA  */
  246.     /* (integer arithmetic) but as UpdateScanLine is much more expensive     */
  247.     /* we will gain almost nothing in speed, doing that.             */
  248.     /* Also as this polygon assumed to intersect with the scan line using    */
  249.     /* integer arithmetic, it might not be so, when we actuallt evaluate it. */
  250.     /* We simply quit if that is the case.                     */
  251.     Coord1 = PScan -> Bndry1.VMinY -> Coord;
  252.     Coord2 = PScan -> Bndry1.VMaxY -> Coord;
  253.     if (ABS(Coord2[1] - Coord1[1]) == 0.0)
  254.     t1 = 0.5;
  255.     else
  256.     t1 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
  257.     if (t1 < 0.0 || t1 > 1.0)
  258.     return;
  259.  
  260.     x1 = Coord1[0] * t1 + Coord2[0] * (1.0 - t1);
  261.     z1 = Coord1[2] * t1 + Coord2[2] * (1.0 - t1);
  262.  
  263.     Coord1 = PScan -> Bndry2.VMinY -> Coord;
  264.     Coord2 = PScan -> Bndry2.VMaxY -> Coord;
  265.     if (ABS(Coord2[1] - Coord1[1]) == 0.0)
  266.     t2 = 0.5;
  267.     else
  268.     t2 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
  269.     if (t2 < 0.0 || t2 > 1.0)
  270.     return;
  271.  
  272.     x2 = Coord1[0] * t2 + Coord2[0] * (1.0 - t2);
  273.     z2 = Coord1[2] * t2 + Coord2[2] * (1.0 - t2);
  274.  
  275.     if (GlblShadeInfo.Gouraud) {
  276.     /* Need to interpolate the colors as well: */
  277.     Color1 = (int) (PScan -> Bndry1.VMinY -> Color * t1 +
  278.             PScan -> Bndry1.VMaxY -> Color * (1.0 - t1));
  279.     Color2 = (int) (PScan -> Bndry2.VMinY -> Color * t2 +
  280.             PScan -> Bndry2.VMaxY -> Color * (1.0 - t2));
  281.     UpdateScanLine(x1, z1, x2, z2, Color1, Color2);
  282.     }
  283.     else {
  284.     /* Flat shading - all vertices has same intensity - pick one: */
  285.     UpdateScanLine(x1, z1, x2, z2, PScan -> Bndry1.VMinY -> Color,
  286.                        PScan -> Bndry1.VMinY -> Color);
  287.     }
  288. }
  289.  
  290. /*****************************************************************************
  291. * Returns the other neighbor of vertex V in polygon PPolygon which is not    *
  292. * the neighbor NotV.                                 *
  293. *****************************************************************************/
  294. static IPVertexStruct *GetNeighborVrtx(IPPolygonStruct *PPolygon,
  295.                        IPVertexStruct *V, IPVertexStruct *NotV)
  296. {
  297.     int i;
  298.     IPVertexStruct *List2,
  299.     *List = PPolygon -> PVertex;
  300.  
  301.     /* Find index of vertex V. */
  302.     for (i = 0; List != V; i++, List = List -> Pnext);
  303.  
  304.     if (i == 0) {
  305.     /* The vertex is first - its neighbors are second and last in list.  */
  306.     if (PPolygon -> PVertex -> Pnext == NotV) {
  307.         /* We need the last one: */
  308.         for (List2 = PPolygon -> PVertex;
  309.          List2 -> Pnext != NULL;
  310.          List2 = List2 -> Pnext);
  311.         return List2;
  312.     }
  313.     else
  314.         return PPolygon -> PVertex -> Pnext;
  315.     }
  316.     else if (List -> Pnext == NULL) {
  317.     /* The vertex is last - its neighbors are first and second from last.*/
  318.     if (PPolygon -> PVertex == NotV) {
  319.         /* We need the second from last: */
  320.         for (List2 = PPolygon -> PVertex;
  321.          List2 -> Pnext != List;
  322.          List2 = List2 -> Pnext);
  323.         return List2;
  324.     }
  325.     else
  326.         return PPolygon -> PVertex;
  327.     }
  328.     else {
  329.     if (List -> Pnext == NotV) {
  330.         for (List2 = PPolygon -> PVertex;
  331.          List2 -> Pnext != List;
  332.          List2 = List2 -> Pnext);
  333.         return List2;
  334.     }
  335.     else
  336.         return List -> Pnext;
  337.     }
  338. }
  339.  
  340. /*****************************************************************************
  341. * Update the scan line itself by linearly interplate the two end points for  *
  342. * all internal points of scan line if closer than old data.             *
  343. *****************************************************************************/
  344. static void UpdateScanLine(int x1, int z1, int x2, int z2,
  345.                         int Color1, int Color2)
  346. {
  347.     int i, Dx, Dz, Dc, Az, Ac, x, z, Color;
  348.     RealType t;
  349.  
  350.     if (x2 < x1) {
  351.     i = x2; x2 = x1; x1 = i;
  352.     i = z2; z2 = z1; z1 = i;
  353.     i = Color2; Color2 = Color1; Color1 = i;
  354.     }
  355.     if (x1 < 0) {
  356.     /* Update lower limit to zero: */
  357.     if (x2 == x1)
  358.         return;
  359.     t = -x1 / (x2 - x1);
  360.     x1 = 0;
  361.     z1 = (int) (z1 * (1.0 - t) + z2 * t);
  362.     Color1 = (int) (Color1 * (1.0 - t) + Color2 * t);
  363.     }
  364.     if (x2 >= GlblShadeInfo.ScrnXSize) {
  365.     /* Update upper limit to GlblShadeInfo.ScrnXSize - 1: */
  366.     if (x2 == x1)
  367.         return;
  368.     t = (x2 - (GlblShadeInfo.ScrnXSize - 1)) / (x2 - x1);
  369.     x2 = GlblShadeInfo.ScrnXSize - 1;
  370.     z2 = (int) (z1 * t + z2 * (1.0 - t));
  371.     Color2 = (int) (Color1 * t + Color2 * (1.0 - t));
  372.     }
  373.  
  374.     Dx = x2 - x1;
  375.     x = x1;
  376.     Dz = z2 - z1;
  377.     Az = -Dx;                  /* DDA accumulator of Z interpolation. */
  378.     z = z1;
  379.     Color = Color1;
  380.     if (GlblShadeInfo.Gouraud) {
  381.     Dc = Color2 - Color1;         /* Needed if Gouraud shading is in use. */
  382.     Ac = -Dx;          /* DDA accumulator of Color interpolation. */
  383.     }
  384.  
  385.     /* We are going to execute the loop once but might be stack forever in   */
  386.     /* one of the internal interplation loops, so make it non zero:         */
  387.     if (Dx == 0)
  388.     Dx = 999;
  389.  
  390.     if (Dz > 0) {
  391.     while (x <= x2) {
  392.         /* Update buffers iff is closer to view point: */
  393.         if (ZBuffer[x] < z) {
  394.         ZBuffer[x] = z;
  395.         ImageScanLine[x] = Color;
  396.         if (MaskScanLine != NULL)
  397.             MaskScanLine[x] = 1;
  398.         }
  399.         else if (ZBuffer[x] == z) {
  400.         /* This case is hard to solve, and it may create high         */
  401.         /* intensity lines on polygon boundaries. To prevent from    */
  402.         /* that, update iff new color intensity is less than old on. */
  403.         if (ImageScanLine[x] < Color)
  404.             ImageScanLine[x] = Color;
  405.         if (MaskScanLine != NULL)
  406.             MaskScanLine[x] = 1;
  407.         }
  408.  
  409.         Az += Dz;
  410.         x++;
  411.         while (Az > 0) {
  412.         z++;
  413.         Az -= Dx;
  414.         }
  415.         if (GlblShadeInfo.Gouraud) {
  416.         if (Dc > 0) {
  417.             Ac += Dc;
  418.             while (Ac > 0) {
  419.             Color++;
  420.             Ac -= Dx;
  421.             }
  422.         }
  423.         else { /* Dc < 0 */
  424.             Ac -= Dc;
  425.             while (Ac > 0) {
  426.             Color--;
  427.             Ac -= Dx;
  428.             }
  429.         }
  430.         }
  431.     }
  432.     }
  433.     else { /* Dz < 0 */
  434.     while (x <= x2) {
  435.         /* Update buffers iff is closer to view point: */
  436.         if (ZBuffer[x] < z) {
  437.         ZBuffer[x] = z;
  438.         ImageScanLine[x] = Color;
  439.         if (MaskScanLine != NULL)
  440.             MaskScanLine[x] = 1;
  441.         }
  442.         else if (ZBuffer[x] == z) {
  443.         /* This case is hard to solve, and it may create high         */
  444.         /* intensity lines on polygon boundaries. To prevent from    */
  445.         /* that, update iff new color intensity is less than old on. */
  446.         if (ImageScanLine[x] < Color)
  447.             ImageScanLine[x] = Color;
  448.         if (MaskScanLine != NULL)
  449.             MaskScanLine[x] = 1;
  450.         }
  451.  
  452.         Az -= Dz;
  453.         x++;
  454.         while (Az > 0) {
  455.         z--;
  456.         Az -= Dx;
  457.         }
  458.         if (GlblShadeInfo.Gouraud) {
  459.         if (Dc > 0) {
  460.             Ac += Dc;
  461.             while (Ac > 0) {
  462.             Color++;
  463.             Ac -= Dx;
  464.             }
  465.         }
  466.         else { /* Dc < 0 */
  467.             Ac -= Dc;
  468.             while (Ac > 0) {
  469.             Color--;
  470.             Ac -= Dx;
  471.             }
  472.         }
  473.         }
  474.     }
  475.     }
  476. }
  477.  
  478. #ifdef DEBUG1
  479.  
  480. /*****************************************************************************
  481. * Routine to print the content of a given edge:                     *
  482. *****************************************************************************/
  483. void PrintHashTable(void)
  484. {
  485.     int i;
  486.     IPPolygonStruct *PPolygon;
  487.  
  488.     for (i = 0; i < GlblShadeInfo.ScrnYSize; i++)
  489.     if (PolyHashTable[i] != NULL) {
  490.         fprintf(stderr,
  491.             "\n***************** HashTable entry %d *****************\n", i);
  492.         PPolygon = PolyHashTable[i];
  493.         while (PPolygon) {
  494.             fprintf(stderr, "\t+++++++ Polygon:\n");
  495.             PrintPolygon(PPolygon);
  496.             PPolygon = PPolygon -> Pnext;
  497.         }
  498.         }
  499. }
  500.  
  501. /*****************************************************************************
  502. * Routine to print the content of a given edge:                     *
  503. *****************************************************************************/
  504. void PrintPolygon(IPPolygonStruct *PPolygon)
  505. {
  506.     int i;
  507.     IPVertexStruct *VList = PPolygon -> PVertex;
  508.  
  509.     for ( ; VList != NULL; VList = VList -> Pnext) {
  510.     fprintf(stderr, "\t%12f %12f %12f (Color = %d).\n",
  511.         PList -> Coord[0],
  512.         PList -> Coord[1],
  513.         PList -> Coord[2],
  514.         PList -> Color);
  515.     }
  516. }
  517.  
  518. /*****************************************************************************
  519. * Routine to print content of Image Scan Line buffer:                 *
  520. *****************************************************************************/
  521. void PrintImageScanLine(void)
  522. {
  523.     int i;
  524.  
  525.     for (i = 0; i < GlblShadeInfo.ScrnXSize; i++) {
  526.     if (i % 26 == 0)
  527.         fprintf(stderr, "\n");
  528.     fprintf(stderr, "%02x ", ImageScanLine[i]);
  529.     }
  530. }
  531.  
  532. #endif /* DEBUG1 */
  533.